import "babel-polyfill";
import {SquarePolynomialZn} from "../polynomial-Zn";
import {exGCD} from "../gcd";

export default class LiftingTree {
    constructor(polynomial, factor_list) {
        this._Type = factor_list[0].constructor;
        this._list = factor_list;
        this._root = this._createTree(0, factor_list.length - 1);
        this._polynomial = polynomial;
    }

    get [Symbol.toStringTag]() {
        return "LiftingTree";
    }

    _createTree(left, right) {
        var node = {};
        if (left === right) {
            node.polynomial = this._list[left];
        } else {
            let mid = (left + right) >>> 1;
            node.left = this._createTree(left, mid);
            node.right = this._createTree(mid + 1, right);
            node.polynomial = this._Type.instance.multiply(node.left.polynomial, node.right.polynomial);
            [, node.left.inverse, node.right.inverse] = this._Type::exGCD(node.left.polynomial, node.right.polynomial);
        }
        return node;
    }

    lift() {
        this._Type = SquarePolynomialZn(this._Type);
        this._root.polynomial = new this._Type(this._polynomial).monic();
        var instance = this._Type.instance;
        var stack = [this._root];
        while (stack.length) {
            let node = stack.pop();
            let F = node.polynomial;
            let [G, H] = [node.left.polynomial, node.right.polynomial];
            let [g, h] = [node.left.inverse, node.right.inverse];
            let A = instance.subtract(F, instance.multiply(G, H));
            let [q, r] = instance.divmod(instance.multiply(g, A), H);
            let degree = G.degree;
            G = instance.add(G, instance.add(
                instance.truncMultiply(h, A, degree),
                instance.truncMultiply(q, G, degree)
            ));
            H = instance.add(H, r);
            let B = instance.subtract(instance.add(instance.multiply(G, g), instance.multiply(H, h)), this._Type.one);
            [q, r] = instance.divmod(instance.multiply(g, B), H);
            g = instance.subtract(g, r);
            h = instance.subtract(h, instance.add(
                instance.truncMultiply(h, B, degree),
                instance.truncMultiply(q, G, degree)
            ));
            [node.left.polynomial, node.right.polynomial] = [G, H];
            [node.left.inverse, node.right.inverse] = [g, h];
            if (node.left.left) {
                stack.push(node.left);
            }
            if (node.right.left) {
                stack.push(node.right);
            }
        }
    }

    *liftResult() {
        var stack = [this._root];
        while (stack.length) {
            let node = stack.pop();
            if (node.left) {
                stack.push(node.right, node.left);
            } else {
                yield node.polynomial;
            }
        }
    }
};
